package 剑指offer;

import java.util.*;


public class p6从尾到头打印链表 {

    //方法一：使用数组先依次存储链表的值，再从尾到头打印数组
    public int[] reversePrint3(ListNode head) {
        ListNode node =head;//创建一个引用指向头结点
        int count=0;//计算链表中的结点个数
        while (node!=null) {
            node=node.next;
            count++;

        }
        node=head;//让node重新指向头结点
        int[] arr=new int[count];
        for (int i=count-1;i>=0;i--) {
            arr[i] = node.val;
            node=node.next;
        }
        return arr;
    }


    public int[] reversePrint2(ListNode head) {
        Stack<ListNode> stack=new Stack<>();//创建 存储结点 的栈
        ListNode node=head;

        while (node!=null) {
            stack.add(node);//将当前 结点 压入栈中
            node=node.next;//当前结点指向下一个结点
        }

        int count=stack.size();//计算栈中元素的个数

        int[] arr=new int[count];

        for (int i=0;i<count;i++) {
            arr[i]=stack.pop().val;//获取 从栈中弹出结点的值
        }

        return arr;
    }


    public int[] reversePrint1(ListNode head) {
        int[] arr={};
        if (head==null) {
            return arr;
        }
        ListNode cur=head;

        Stack<Integer> stack=new Stack<>();
        while (cur!=null) {
            stack.add(cur.val);
            cur=cur.next;
        }

        int size=stack.size();
        arr=new int[size];

        for (int i = 0; i <size; i++) {
            arr[i]=stack.pop();
        }
        return arr;
    }


    List<Integer> res=new ArrayList<>();
    public int[] reversePrint4(ListNode head) {
        //回溯算法
        backTrack(head);
        int[] result=new int[res.size()];
        for (int i = 0; i <res.size(); i++) {
            result[i]=res.get(i);
        }
        return result;
    }

    private void backTrack(ListNode node) {
        if (node==null) {
            return;
        }
        //递归
        backTrack(node.next);
        //回溯
        res.add(node.val);
    }

    public int[] reversePrint(ListNode head) {
        //辅助栈
        Deque<Integer> stack=new ArrayDeque<>();
        while (head!=null) {
            stack.addLast(head.val);
            head=head.next;
        }

        int[] res=new int[stack.size()];
        for (int i = 0; i <res.length; i++) {
            res[i]=stack.removeLast();
        }
        return res;
    }
}
